/*
数据结构实验第一题 ，合并有序数组
 采用静态顺序表
 CMake如下
cmake_minimum_required(VERSION 3.27)
project(merge_linerlist)
set(CMAKE_CXX_STANDARD 17)
add_executable(merge_linerlist main.c)

*/
#include <stdio.h>
#define MAXNUM 30//定义最大顺序表的长度

typedef int ElemType;
//顺序表定义如下
typedef struct{
	ElemType arry[MAXNUM];//数据域
	int length;           //有效长度
}SqList , *SeqList;
//函数声明
void InsertSqList (SqList *L , int x );//将数据插入顺序表中
void merge (SqList *L , SqList *M , SqList *N);//执行合并操作
void output (SqList *N);//进行格式化输出
//程序入口
int main ()
{   //定义三个顺序表
	SqList first;
	SqList second;
	SqList third;
	//初始化三个顺序表
	second.length = 0;
	first.length = 0;
	third.length = 0;
	//定义两个顺序表的输入长度
	int n , m;
	scanf ("%d" , &n);
	//两个已知有序数组的输入
	int tem;
	for (int i = 0 ; i < n ; i++)
	{

		scanf ("%d" , &tem);
		InsertSqList (&first , tem );
	}
	scanf ("%d" , &m);
	int temp;
	for (int j = 0 ; j < m ; j++)
	{
		scanf ("%d" , &temp);
		InsertSqList (&second ,temp);
	}
	merge(&first , &second , &third);//执行合并操作
	output(&third);//输出
	return 0;
}
//执行顺序表的插入操作（尾插）
void InsertSqList (SqList *L , int x )
{
	L->arry[L->length] = x;
	L->length++;
}
//执行合并操作
//输入两个有序数组，合并为一个有序数组
void merge (SqList *L , SqList *M , SqList *N)
{
	int i = 0, j = 0 , k = 0;
	while (i < L->length && j < M->length)
	{
		if(L->arry[i] <= M->arry[j])
		{
			N->arry[k] = L->arry[i];
			k++;
			i++;
		}
		else
		{
			N->arry[k] = M->arry[j];
			k++;
			j++;
		}
	}
	//处理合并之后两个之中余下的那个有序表
	while (i <L->length)
	{
		N->arry[k] = L->arry[i];
		i++;
		k++;
	}
	while (j < M->length)
	{
		N->arry[k] = M->arry[j];
		j++;
		k++;
	}
	N->length = k;//更新顺序表长度
}
//进行格式化输出
void output (SqList *N)
{
	int len = N->length;
	for (int i = 0 ; i < len ; i++ )
		printf ("%d\n" , N->arry[i]);
}
